{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Score of All Prefixes of an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findPrefixScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #一个数组所有前缀的分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>定义一个数组 <code>arr</code>&nbsp;的 <strong>转换数组</strong>&nbsp;<code>conver</code>&nbsp;为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>conver[i] = arr[i] + max(arr[0..i])</code>，其中&nbsp;<code>max(arr[0..i])</code>&nbsp;是满足 <code>0 &lt;= j &lt;= i</code>&nbsp;的所有&nbsp;<code>arr[j]</code>&nbsp;中的最大值。</li>\n",
    "</ul>\n",
    "\n",
    "<p>定义一个数组 <code>arr</code>&nbsp;的 <strong>分数</strong>&nbsp;为 <code>arr</code>&nbsp;转换数组中所有元素的和。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>nums</code>&nbsp;，请你返回一个长度为 <code>n</code>&nbsp;的数组<em>&nbsp;</em><code>ans</code>&nbsp;，其中&nbsp;<code>ans[i]</code>是前缀&nbsp;<code>nums[0..i]</code>&nbsp;的分数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,3,7,5,10]\n",
    "<b>输出：</b>[4,10,24,36,56]\n",
    "<b>解释：</b>\n",
    "对于前缀 [2] ，转换数组为 [4] ，所以分数为 4 。\n",
    "对于前缀 [2, 3] ，转换数组为 [4, 6] ，所以分数为 10 。\n",
    "对于前缀 [2, 3, 7] ，转换数组为 [4, 6, 14] ，所以分数为 24 。\n",
    "对于前缀 [2, 3, 7, 5] ，转换数组为 [4, 6, 14, 12] ，所以分数为 36 。\n",
    "对于前缀 [2, 3, 7, 5, 10] ，转换数组为 [4, 6, 14, 12, 20] ，所以分数为 56 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,1,2,4,8,16]\n",
    "<b>输出：</b>[2,4,8,16,32,64]\n",
    "<b>解释：</b>\n",
    "对于前缀 [1] ，转换数组为 [2] ，所以分数为 2 。\n",
    "对于前缀 [1, 1]，转换数组为 [2, 2] ，所以分数为 4 。\n",
    "对于前缀 [1, 1, 2]，转换数组为 [2, 2, 4] ，所以分数为 8 。\n",
    "对于前缀 [1, 1, 2, 4]，转换数组为 [2, 2, 4, 8] ，所以分数为 16 。\n",
    "对于前缀 [1, 1, 2, 4, 8]，转换数组为 [2, 2, 4, 8, 16] ，所以分数为 32 。\n",
    "对于前缀 [1, 1, 2, 4, 8, 16]，转换数组为 [2, 2, 4, 8, 16, 32] ，所以分数为 64 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-score-of-all-prefixes-of-an-array](https://leetcode.cn/problems/find-the-score-of-all-prefixes-of-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-score-of-all-prefixes-of-an-array](https://leetcode.cn/problems/find-the-score-of-all-prefixes-of-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,7,5,10]', '[1,1,2,4,8,16]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        numMax = nums[0]\n",
    "        coverSum = 0\n",
    "        for i in range(len(nums)):\n",
    "            numMax = max(numMax, nums[i])\n",
    "            cover = nums[i] + numMax\n",
    "            coverSum += cover\n",
    "            nums[i] = coverSum\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        numMax = nums[0]\n",
    "        coverSum = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > numMax:\n",
    "                numMax = nums[i]\n",
    "            coverSum += nums[i] + numMax\n",
    "            nums[i] = coverSum\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        numMax = nums[0]\n",
    "        coverSum = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > numMax:\n",
    "                numMax = nums[i]\n",
    "            coverSum += nums[i] + numMax\n",
    "            nums[i] = coverSum\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        numMax = nums[0]\n",
    "        coverSum = 0\n",
    "        for i in range(len(nums)):\n",
    "            numMax = max(numMax, nums[i])\n",
    "            coverSum += nums[i] + numMax\n",
    "            nums[i] = coverSum\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        mx = 0\n",
    "        for i in range(len(nums)):\n",
    "            mx = max(mx, nums[i])\n",
    "            nums[i] += mx\n",
    "        for i in range(1,len(nums)):\n",
    "            nums[i] += nums[i-1]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        x = nums[0]\n",
    "        nums[0] += x\n",
    "        for i in range(1, len(nums)):\n",
    "            x = max(x, nums[i])\n",
    "            nums[i] += nums[i-1] + x\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0]*len(nums)        \n",
    "        max1 = nums[0]\n",
    "        ans[0] = 2*nums[0]        \n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > max1:\n",
    "                max1 = nums[i]\n",
    "            conver_c = nums[i] + max1\n",
    "            ans[i] = ans[i-1] + conver_c\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0]*len(nums)        \n",
    "        max1 = nums[0]\n",
    "        ans[0] = 2*nums[0]\n",
    "        conver_c = ans[0]\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > max1:\n",
    "                max1 = nums[i]\n",
    "            conver_c = nums[i] + max1\n",
    "            ans[i] = ans[i-1] + conver_c\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ans=[0]*n\n",
    "        mx=total=0\n",
    "        for i,x in enumerate(nums):\n",
    "            mx=max(x,mx)\n",
    "            total+=x+mx\n",
    "            ans[i]=total\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [0] * n\n",
    "        m = nums[0]\n",
    "        res[0] = m * 2\n",
    "        for i in range(1, n):\n",
    "            m = max(m, nums[i])\n",
    "            res[i] = res[i-1] + m + nums[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        premax = 0\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        presum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            premax = max(premax, x)\n",
    "            ans[i] = x + premax + presum\n",
    "            presum = ans[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        origin = nums[::]\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] = max(nums[i], nums[i - 1])\n",
    "        cur = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            cur += n + origin[i]\n",
    "            res.append(cur)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        mx = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            mx = max(mx, x)\n",
    "            nums[i] += mx\n",
    "\n",
    "        return list(accumulate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        origin = nums[::]\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] = max(nums[i], nums[i - 1])\n",
    "        cur = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            cur += n + origin[i]\n",
    "            res.append(cur)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        conver = []\n",
    "        max_val = 0\n",
    "        for num in nums:\n",
    "            if max_val < num:\n",
    "                max_val = num\n",
    "            conver.append(max_val + num)\n",
    "        for i in range(1, len(conver)):\n",
    "            conver[i] = conver[i] + conver[i - 1]\n",
    "        return conver\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        result = []\n",
    "        max_value = nums[0]\n",
    "        sum_value = 0\n",
    "        for num in nums:\n",
    "            if num > max_value:\n",
    "                max_value = num\n",
    "            result.append(num + max_value + sum_value)\n",
    "            sum_value += num + max_value\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        sum1 = maxnum = 0\n",
    "        for i in range(len(nums)):\n",
    "            maxnum = max(maxnum,nums[i])\n",
    "            sum1+=maxnum+nums[i]\n",
    "            res.append(sum1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        temp_max = 0\n",
    "        temp_res = 0\n",
    "        for num in nums:\n",
    "            temp_max = max(temp_max, num)\n",
    "            temp_res += num + temp_max\n",
    "            res.append(temp_res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        sum1 = maxnum = 0\n",
    "        for i in range(len(nums)):\n",
    "            maxnum = max(maxnum,nums[i])\n",
    "            sum1+=maxnum+nums[i]\n",
    "            res.append(sum1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        maxVal = -1\n",
    "        s = 0\n",
    "\n",
    "        ans = [0 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            maxVal = max(nums[i],maxVal)\n",
    "            s += nums[i] + maxVal\n",
    "            ans[i] = s\n",
    "    \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        maxn = 0\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            maxn = max(maxn, x)\n",
    "            ans[i] = ans[i - 1] + x + maxn\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        p, m = 0, 0\n",
    "        cores = []\n",
    "        for num in nums:\n",
    "            if num > m:\n",
    "                m = num\n",
    "            p += num + m\n",
    "            cores.append(p)\n",
    "        return cores\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        s=nums[0]\n",
    "        n=len(nums)\n",
    "        ans=[0]*n\n",
    "        ans[0]=nums[0]*2\n",
    "        for i in range(n):\n",
    "          s=max(s,nums[i])\n",
    "          \n",
    "          if i>0:   \n",
    "           ans[i]=s+nums[i]+ans[i-1]\n",
    "            \n",
    "       \n",
    "        return ans    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        cur_max = float(\"-inf\")\n",
    "        pre_sum = 0\n",
    "        scores = [0 for _ in range(len(nums))]\n",
    "        cvt = [0 for _ in range(len(nums))]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > cur_max:\n",
    "                cur_max = nums[i]\n",
    "            pre_sum += (nums[i] + cur_max)\n",
    "            scores[i] = pre_sum\n",
    "        return scores\n",
    "\n",
    "# class Solution:\n",
    "#     def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "#         ans, ma = [nums[0] << 1], nums[0]\n",
    "#         for n in nums[1:]:\n",
    "#             if n > ma: ma = n\n",
    "#             ans.append(ans[-1] + n + ma)\n",
    "#         return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        mx = float('-inf')\n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            mx = max(mx,nums[i])\n",
    "            conv = mx + nums[i]\n",
    "            if len(ans)==0:\n",
    "                ans.append(conv)\n",
    "            else:\n",
    "                ans.append(conv+ans[-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        conver = 0\n",
    "\n",
    "        max_num = nums[0]\n",
    "\n",
    "        ret = []\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            max_num = max(max_num,nums[i])\n",
    "            conver += max_num+nums[i]\n",
    "            ret.append(conver)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        arr=0\n",
    "        ans=[]\n",
    "        max_num=0\n",
    "        for i in nums:\n",
    "            max_num=max(max_num,i)\n",
    "            arr=arr+i+max_num\n",
    "            ans.append(arr)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        arr=0\n",
    "        ans=[]\n",
    "        max_num=0\n",
    "        for i in nums:\n",
    "            max_num=max(max_num,i)\n",
    "            arr=arr+i+max_num\n",
    "            ans.append(arr)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        arr=0\n",
    "        ans=[]\n",
    "        max_num=0\n",
    "        for i in nums:\n",
    "            max_num=max(max_num,i)\n",
    "            arr=arr+i+max_num\n",
    "            ans.append(arr)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        res = [0] * len(nums)\n",
    "        num_max = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > num_max:\n",
    "                num_max = nums[i]\n",
    "            if i == 0:\n",
    "                res[i] = nums[i] + num_max\n",
    "            else:\n",
    "                res[i] = nums[i] + num_max + res[i - 1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        nums_len = len(nums)\n",
    "        max_pre = [0]*nums_len\n",
    "        t_max = nums[0]\n",
    "        ans = [0]*nums_len\n",
    "        for i in range(nums_len):\n",
    "            v = nums[i]\n",
    "            if v>t_max:\n",
    "                t_max = v\n",
    "            max_pre[i] = t_max\n",
    "        pre = [0]*(nums_len+1)\n",
    "        for i in range(1, nums_len+1):\n",
    "            v = nums[i-1]\n",
    "            pre[i] = pre[i-1]+v+max_pre[i-1]\n",
    "            ans[i-1] = pre[i]\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        mx = s = 0\n",
    "        for x in nums:\n",
    "            mx = max(mx, x)  # 前缀最大值\n",
    "            s += x + mx  # 累加前缀的得分\n",
    "            ans.append(s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        mx,s=0,0\n",
    "        for x in nums:\n",
    "            mx=max(mx,x)\n",
    "            s+=x+mx\n",
    "            ans.append(s)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        pre = float('-inf')\n",
    "        presum = 0\n",
    "        for i in range(len(nums)):\n",
    "            pre = max(pre, nums[i])\n",
    "            val = nums[i] + pre\n",
    "            presum += val\n",
    "            ans.append(presum)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        mx = 0\n",
    "        sm = 0\n",
    "        i = 0\n",
    "        ans = [0] * len(nums)\n",
    "        for num in nums:\n",
    "            mx = max(mx, num)\n",
    "            sm += num + mx\n",
    "            ans[i] = sm\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        mx = s = 0\n",
    "\n",
    "        for x in nums:\n",
    "\n",
    "            mx = max(mx, x)\n",
    "            s += x + mx\n",
    "            ans.append(s)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        mx = s = 0\n",
    "        for x in nums:\n",
    "            mx = max(mx, x)  # 前缀最大值\n",
    "            s += x + mx  # 累加前缀的得分\n",
    "            ans.append(s)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        arr = []\n",
    "        max_v = nums[0]\n",
    "        ans = []\n",
    "        tol = 0\n",
    "        for c in nums:\n",
    "            max_v = max(max_v, c)\n",
    "            tol += max_v + c\n",
    "            ans.append(tol)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        pre=nums[0]\n",
    "        n=len(nums)\n",
    "        ans=[]\n",
    "        tot=0\n",
    "        for i in range(n):\n",
    "            pre=max(pre,nums[i])\n",
    "            tot+=nums[i]+pre\n",
    "            ans.append(tot)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        cover = [0 for _ in range(len(nums))]\n",
    "        maxValue = 0\n",
    "        for i in range(len(nums)):\n",
    "            maxValue = max(maxValue, nums[i])\n",
    "            cover[i] = nums[i] + maxValue\n",
    "\n",
    "        # for i in range(1, len(nums)):\n",
    "            if i > 0:\n",
    "                cover[i] += cover[i-1] \n",
    "\n",
    "        return cover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        maxi, pre, res = nums[0], 2 * nums[0], []\n",
    "        res.append(pre)\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > maxi:\n",
    "                pre += 2 * nums[i]\n",
    "                maxi = nums[i]\n",
    "                res.append(pre)\n",
    "            else:\n",
    "                pre += nums[i] + maxi\n",
    "                res.append(pre)\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        a = nums[0]\n",
    "        b = 0\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            a = max(a, nums[i])\n",
    "            if i > 0:\n",
    "                b = nums[i] + a + res[i - 1]\n",
    "            else:\n",
    "                b = nums[i] + a\n",
    "            res.append(b)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        cover = [0 for _ in range(len(nums))]\n",
    "        maxValue = 0\n",
    "        for i in range(len(nums)):\n",
    "            maxValue = max(maxValue, nums[i])\n",
    "            cover[i] = nums[i] + maxValue\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            cover[i] += cover[i-1] \n",
    "\n",
    "        return cover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        convert = []\n",
    "        max_ = 0\n",
    "        for i , x in enumerate(nums) :\n",
    "            max_ = max(max_ , x) \n",
    "            convert.append(x + max_)\n",
    "            \n",
    "        for i in range(1,len(convert)):\n",
    "            convert[i] += convert[i-1]\n",
    "        return convert"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        return [*accumulate(map(add, nums, accumulate(nums, max)))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        cur_max = float(\"-inf\")\n",
    "        pre_sum = 0\n",
    "        scores = [0 for _ in range(len(nums))]\n",
    "        # cvt = [0 for _ in range(len(nums))]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > cur_max:\n",
    "                cur_max = nums[i]\n",
    "            pre_sum += (nums[i] + cur_max)\n",
    "            scores[i] = pre_sum\n",
    "        return scores\n",
    "\n",
    "# class Solution:\n",
    "#     def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "#         ans, ma = [nums[0] << 1], nums[0]\n",
    "#         for n in nums[1:]:\n",
    "#             if n > ma: ma = n\n",
    "#             ans.append(ans[-1] + n + ma)\n",
    "#         return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        max_val = nums[0]\n",
    "        prefix_sum = 0\n",
    "        for num in nums:\n",
    "            max_val = max(max_val, num)\n",
    "            prefix_sum += num + max_val\n",
    "            ans.append(prefix_sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        mx, s = 0, 0\n",
    "        for x in nums:\n",
    "            mx = max(mx, x)\n",
    "            s += mx + x\n",
    "            ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        maxnum = 0\n",
    "        ans = []\n",
    "        sunnum = 0\n",
    "        for i in nums:\n",
    "            maxnum = max(i,maxnum)\n",
    "            temp = i + maxnum\n",
    "            sunnum += temp\n",
    "            ans.append(sunnum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        m = 0\n",
    "        for i in range(len(nums)):\n",
    "            m = max(m,nums[i])\n",
    "            if not ans:\n",
    "                t = 0\n",
    "            else:\n",
    "                t = ans[-1]\n",
    "            t += nums[i] + m\n",
    "            ans.append(t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        max_val = nums[0]\n",
    "        prefix_sum = 0\n",
    "        for num in nums:\n",
    "            max_val = max(max_val, num)\n",
    "            prefix_sum += num + max_val\n",
    "            ans.append(prefix_sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/find-the-score-of-all-prefixes-of-an-array/description/\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        n = nums.__len__()\n",
    "        res, pres = [nums[0]*2], [nums[0]]\n",
    "        mx = nums[0]\n",
    "        for i in range(1, n):\n",
    "            num = nums[i]\n",
    "            if mx < num:\n",
    "                mx = num\n",
    "            pres.append(mx)\n",
    "            res.append(res[i-1] + num + mx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        result = [0]\n",
    "        dpmax = [nums[0]]\n",
    "        for i in range(1,n):\n",
    "            dpmax.append(max(dpmax[-1],nums[i]))\n",
    "        for i in range(n):\n",
    "            result.append(result[-1]+nums[i]+dpmax[i])\n",
    "        return result[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        if len(nums) == 0:\n",
    "            return []\n",
    "\n",
    "        conver = [0] * len(nums)\n",
    "        maxs = [0] * len(nums)\n",
    "        conver[0] = nums[0] * 2\n",
    "        maxs[0] = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > maxs[i - 1]:\n",
    "                maxs[i] = nums[i]\n",
    "                conver[i] = nums[i] + maxs[i]\n",
    "            else:\n",
    "                maxs[i] = maxs[i - 1]\n",
    "                conver[i] = maxs[i - 1] + nums[i]\n",
    "\n",
    "        ans = [0] * len(nums)\n",
    "        ans[0] = conver[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            ans[i] = ans[i - 1] + conver[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        cur_max = nums[0]\n",
    "        arr = [2*nums[0]]\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            cur_max = max(cur_max, nums[i])\n",
    "            arr.append(cur_max + nums[i]) \n",
    "        return list(accumulate(arr))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0]*len(nums)\n",
    "        conver = [0]*len(nums)\n",
    "        max1 = nums[0]\n",
    "        ans[0] = 2*nums[0]\n",
    "        conver[0] = ans[0]\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] > max1:\n",
    "                max1 = nums[i]\n",
    "            conver[i] = nums[i] + max1\n",
    "            ans[i] = ans[i-1] + conver[i]\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        mx = []\n",
    "        for n in nums:\n",
    "            if not mx:\n",
    "                mx.append(n)\n",
    "            else:\n",
    "                mx.append(max(mx[-1], n))\n",
    "                \n",
    "        for i, n in enumerate(nums):\n",
    "            mx[i] += n\n",
    "        \n",
    "        # print(mx)\n",
    "        return list(itertools.accumulate(mx))\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        res=[]\n",
    "        ans=[0]*len(nums)\n",
    "        maxNum=nums[0]\n",
    "        for i in range(len(nums)):\n",
    "            maxNum=max(nums[i],maxNum)\n",
    "            res+=[nums[i]+maxNum]\n",
    "        ans[0]=res[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            ans[i]=ans[i-1]+res[i]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        conver=[0]*n\n",
    "        mx=0\n",
    "        for i,x in enumerate(nums):\n",
    "            mx=max(x,mx)\n",
    "            conver[i]=x+mx\n",
    "        # print(conver)\n",
    "        ans=[0]*n\n",
    "        total=0\n",
    "        for i,x in enumerate(conver):\n",
    "            total+=x\n",
    "            ans[i]=total\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        big = 0\n",
    "        # 转换数组\n",
    "        conver = []\n",
    "        for n in nums:\n",
    "            big = max(big, n)\n",
    "            conver.append(n + big)\n",
    "        return list(accumulate(conver))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        pre=[0]*n\n",
    "        m=[0]*n\n",
    "        cov=[0]*n\n",
    "        m[0]=nums[0]\n",
    "        cov[0]=nums[0]*2\n",
    "        for i in range(1,n):\n",
    "            m[i]=max(m[i-1],nums[i])\n",
    "            cov[i]=nums[i]+m[i]\n",
    "        pre[0]=cov[0]\n",
    "        for i in range(1,n):\n",
    "            pre[i]+=pre[i-1]+cov[i]\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        premax = 0\n",
    "        presum = 0\n",
    "        ans = []\n",
    "        temp = []\n",
    "        for i in range(len(nums)):\n",
    "            temp.append(nums[i] + max(premax, nums[i]))\n",
    "            presum += temp[-1]\n",
    "            ans.append(presum)\n",
    "            premax = max(nums[i], premax)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPrefixScore(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ans=[0]*n\n",
    "        mmax=0\n",
    "        for i,x in enumerate(nums):\n",
    "            mmax=max(mmax,x)\n",
    "            ans[i]=x+mmax\n",
    "        return list(accumulate(ans))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
